#include "BTreeNode.h"
#include <stdio.h>
#include <cstdlib>
#include <math.h>

#define GREATER_SATISFIED -1000
#define LESS_SATISFIED -1001
#define GREATEREQUAL_SATISFIED -1002
#define LESSEQUAL_SATISFIED -1003
#define INEQUALITY_NOT_SATISFIED -1004
#define EQUALITY_NOT_SATISFIED -1005


using namespace std;

void BTLeafNode::leafSwap(void *arr, int i, int j) {
    int temp_key, *temp_rid;

    temp_rid = (int*) malloc(2 * sizeof (int));

    //key swap
    memcpy(&temp_key, arr + 4 * sizeof (int) +i * 3 * sizeof (int), sizeof (int));
    memcpy(arr + 4 * sizeof (int) +i * 3 * sizeof (int), arr + 4 * sizeof (int) +j * 3 * sizeof (int), sizeof (int));
    memcpy(arr + 4 * sizeof (int) +j * 3 * sizeof (int), &temp_key, sizeof (int));

    //rid swap
    memcpy(temp_rid, arr + 4 * sizeof (int) +i * 3 * sizeof (int) + sizeof (int), 2 * sizeof (int));
    memcpy(arr + 4 * sizeof (int) +i * 3 * sizeof (int) + sizeof (int), arr + 4 * sizeof (int) +j * 3 * sizeof (int), 2 * sizeof (int));
    memcpy(arr + 4 * sizeof (int) +j * 3 * sizeof (int) + sizeof (int), temp_rid, 2 * sizeof (int));

    
    
    
}

void BTNonLeafNode::nonLeafSwap(void *arr, int i, int j) {
    int temp_key, temp_pid;

    //key swap
    memcpy(&temp_key, arr + 4 * sizeof (int) +i * 2 * sizeof (int), sizeof (int));
    memcpy(arr + 4 * sizeof (int) +i * 2 * sizeof (int), arr + 4 * sizeof (int) +j * 2 * sizeof (int), sizeof (int));
    memcpy(arr + 4 * sizeof (int) +j * 2 * sizeof (int), &temp_key, sizeof (int));

    //pid swap
    memcpy(&temp_pid, arr + 4 * sizeof (int) +i * 2 * sizeof (int) + sizeof (int), sizeof (int));
    memcpy(arr + 4 * sizeof (int) +i * 2 * sizeof (int) + sizeof (int), arr + 4 * sizeof (int) +j * 2 * sizeof (int) + sizeof(int), sizeof (int));
    memcpy(arr + 4 * sizeof (int) +j * 2 * sizeof (int) + sizeof (int), &temp_pid, sizeof (int));

    
    
    
}

RC BTLeafNode::leafSort(void *temp) {

    int i, j, count, ai, aj;
    memcpy(&count, temp + 3 * sizeof (int), sizeof (int));

    for (int i = 0; i < count; i++) {
        for (j = i + 1; j < count; j++) {

            memcpy(&ai, temp + 4 * sizeof (int) +i * 3 * sizeof (int), sizeof (int));
            memcpy(&aj, temp + 4 * sizeof (int) +j * 3 * sizeof (int), sizeof (int));

            if (ai > aj) {
                BTLeafNode::leafSwap(&temp, i, j);
            }

        }
    }

    
    
    
}

RC BTNonLeafNode::nonLeafSort(void *temp) {


    int i, j, count, ai, aj;
    memcpy(&count, temp + 3 * sizeof (int), sizeof (int));

    for (int i = 0; i < count; i++) {
        for (j = i + 1; j < count; j++) {

            //temp+3 ints (the metadata )+ 1 int (1st page id)
            memcpy(&ai, temp + 4 * sizeof (int) +i * 2 * sizeof (int), sizeof (int));
            memcpy(&aj, temp + 4 * sizeof (int) +j * 2 * sizeof (int), sizeof (int));

            if (ai > aj) {
                BTNonLeafNode::nonLeafSwap(&temp, i, j);
            }

        }
    }

    
    
    
    
}

RC BTLeafNode::BTLeafNode(PageId ppid, PageId pid, PageId siblingId) {

    numkeys = 0;
    memcpy(buffer, &ppid, sizeof (int));
    memcpy((buffer + sizeof (int)), &pid, sizeof (int));
    memcpy((buffer + 2 * sizeof (int)), &numkeys, sizeof (int));
    memcpy((buffer + 3 * sizeof (int)), &siblingId, sizeof (int));

    hashmap[pid] = 'L';
    
    
    
    
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf) {

    return 0;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf) {

    return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount() {
    return 0;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
int BTLeafNode::insert(int key, const RecordId& rid, PageFile &pf, PageId rootPid) {

    void *temp, *parentBuffer, nodeToInsert_buffer;
    int key_pushed, cursor, currentNumberOfKeys;
    int newroot, oldNodeCount, parentid;
    pf.read(rootPid, temp);

    //modify temp here to include the new (key,pid,sid) triple

    memcpy(&oldNodeCount, temp + 2 * sizeof (int), sizeof (int));

    if (hashmap[rootPid] == 'L') {
        if (oldNodeCount < MAX_LEAF) {

            memcpy(temp + 4 * sizeof (int) +oldNodeCount * 3 * sizeof (int), &key, sizeof (int));
            memcpy((temp + 4 * sizeof (int) +oldNodeCount * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));

        }
        else {

            //special case of insert and split
            int newNodeId = pf.endPid();
            int newPPid = -1, newSiblingId = -1;
            BTLeafNode newSplitNode(newPPid, newNodeId, newSiblingId);

            memcpy(temp + 4 * sizeof (int) +oldNodeCount * 3 * sizeof (int), &key, sizeof (int));
            memcpy((temp + 4 * sizeof (int) +oldNodeCount * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));

            // sort(temp);

            /**
             * INSERT AND SPLIT FUNCTION CODE BELOW:
             * prevNodeCount:Now how much will remain in old node
             * newNodeCount: how many in new node
             */

            int prevNodeCount = ceil((oldNodeCount + 1) / 2);
            int newNodeCount = oldNodeCount - prevNodeCount + 1;


            /*Copying the metadata into the old node and the newly split node*/
            memcpy(temp + 2 * sizeof (int), &prevNodeCount, sizeof (int));

            memcpy(newSplitNode.buffer + 2 * sizeof (int), &newNodeCount, sizeof (int));

            memcpy(temp + 3 * sizeof (int), newNodeId, sizeof (int));


            int our_index = ((prevNodeCount + 1) * sizeof (int) * 3) + 4 * sizeof (int), j = 4 * sizeof (int);

            while (our_index <= (MAX_LEAF + 1)*3 * sizeof (int) + 4 * sizeof (int)) {
                /*
                 * first iteration. key_pushed variable 
                 * contains the 1st data of the new node, 
                 * which needs to be copied to the parent
                 */
                if (j == 4 * sizeof (int)) {
                    memcpy(&key_pushed, temp + our_index, sizeof (int));
                }

                memcpy(newSplitNode.buffer + j, temp + our_index, 3 * sizeof (int));

                our_index += 3 * sizeof (int);

                j += 3 * sizeof (int);

            }

            pf.write(newNodeId, newSplitNode.buffer);

            newroot = pf.endPid();

            BTNonLeafNode btnl = new BTNonLeafNode(-1, newroot);

            btnl.initializeRoot(rootPid, key_pushed, newNodeId);

            memcpy(temp, &newroot, sizeof (int));

            memcpy(newSplitNode.buffer, &newroot, sizeof (int));

            pf.write(newroot, btnl.getBuffer());

            pf.write(newNodeId, newSplitNode.buffer);
        }

        pf.write(rootPid, temp);

        rootPid = newroot;

    }
    else {
        //general case for insert and split
        //hashmap['rootpid']='N'
        cursor = rootPid;

        while (hashmap[cursor] != 'L') {
            BTNonLeafNode::locateChildPtr(key, &cursor);
        }
        /* now cursor has the page id of the leaf node in which we should insert
         * the Key.
         * Next we read the contents of the page (pointed to by cursor),
         * into nodeToInsert_buffer
         * 
         */
        pf.read(cursor, nodeToInsert_buffer);

        memcpy(&currentNumberOfKeys, nodeToInsert_buffer + 2 * sizeof (int), sizeof (int));

        if (currentNumberOfKeys < MAX_LEAF) {
            //insert into this node and sort

            memcpy(nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int), &key, sizeof (int));

            memcpy((nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));

            BTLeafNode::leafSort(nodeToInsert_buffer);
            //SORT!!!

        } else {
            //insert and split


            /****************************************************************/

            //special case of insert and split
            int newNodeId = pf.endPid();
            int newPPid = -1, newSiblingId = -1;

            BTLeafNode newSplitNode(newPPid, newNodeId, newSiblingId);

            memcpy(nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int), &key, sizeof (int));

            memcpy((nodeToInsert_buffer + 4 * sizeof (int) +currentNumberOfKeys * 3 * sizeof (int) + sizeof (int)), &rid, (2 * sizeof (int)));
            // sort(temp);
            BTLeafNode::leafSort(nodeToInsert_buffer);

            /**
             * INSERT AND SPLIT FUNCTION CODE BELOW:
             * prevNodeCount:Now how much will remain in old node
             * newNodeCount: how many in new node
             */

            int prevNodeCount = ceil((currentNumberOfKeys + 1) / 2);

            int newNodeCount = currentNumberOfKeys - prevNodeCount + 1;


            //call the insert and split function here
            int numberOfParentElements = BTLeafNode::insertAndSplit(prevNodeCount, &parentid, newNodeCount,
                    newNodeId, newSplitNode, nodeToInsert_buffer, cursor, &pf);


            //NOW CHECK FOR NON LEAF OVERFLOW
            if (numberOfParentElements > MAX_NONLEAF) {
                // INSERT AND SPLIT NON LEAF
                BTNonLeafNode::insertAndSplit(parentid, &pf, &rootPid);

            }


        }
    }

    
    
    
    
    
    
    
    return rootPid;
    
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */

/* ----OLD insertAndSplit Definition-- Given by Chu-Cheng
 * RC BTLeafNode::insertAndSplit(int key, const RecordId& rid,
        BTLeafNode& sibling, int& siblingKey) 
 */

RC BTLeafNode::insertAndSplit(int prevNodeCount, int &parentid, int newNodeCount, int newNodeId, BTLeafNode newSplitNode,
        void *nodeToInsert_buffer, int cursor, PageFile &pf) {

    int old_sibling_id,  key_above;
    void *parentBuffer;

    /*Copying the Metadata into my old and new leaf nodes
     */

    memcpy(nodeToInsert_buffer + 2 * sizeof (int), &prevNodeCount, sizeof (int));

    memcpy(newSplitNode.buffer + 2 * sizeof (int), &newNodeCount, sizeof (int));

    /*setting the sibling ids of the old and new node
     */
    memcpy(&old_sibling_id, nodeToInsert_buffer + 3 * sizeof (int), sizeof (int));

    memcpy(nodeToInsert_buffer + 3 * sizeof (int), newNodeId, sizeof (int));

    memcpy(newSplitNode.buffer + 3 * sizeof (int), old_sibling_id, sizeof (int));

    int our_index = ((prevNodeCount + 1) * sizeof (int) * 3) + 4 * sizeof (int), j = 4 * sizeof (int);

    /*Our_Index : Points to the Middle of the Old Node
     * we take this Our_index to the End of the Old node and copy these elements
     * into the new node
     */
    while (our_index <= (MAX_LEAF + 1)*3 * sizeof (int) + 4 * sizeof (int)) {
        if (j == 4 * sizeof (int)) //first iteration
        {
            memcpy(&key_above, nodeToInsert_buffer + our_index, sizeof (int));
        }

        memcpy(newSplitNode.buffer + j, nodeToInsert_buffer + our_index, 3 * sizeof (int));

        our_index += 3 * sizeof (int);

        j += 3 * sizeof (int);
    }

    /***DONE WITH THE COPY OF HALF THE ELEMENTS****/

    /*Setting the new node's parent ID to the old node's parent ID*/
    memcpy(&parentid, nodeToInsert_buffer, sizeof (int));

    memcpy(newSplitNode.buffer, &parentid, sizeof (int));


    /*Writing the data back to the DISK*/

    pf.write(cursor, nodeToInsert_buffer);
    pf.write(newNodeId, newSplitNode.buffer);

    /****************************************************************/

    int numberOfParentElements = BTNonLeafNode::insert(key_above, newNodeId,
            parentid, &pf);

    
    
    
    
    
    
    
    

    return numberOfParentElements;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * 
 * @return 0 if successful. Return an error code if there is an error.
 * -1 : NO RECORDS FOUND. EQUALITY CASE
 * -1000 : INEQUALITY CONDITION SATISFIED
 
 */
RC BTLeafNode::locate(int searchKey, int& eid, PageId pid, PageFile &pf, int op) {

    int j = 0, tempKey, number_of_keys, siblingId;
    void *leafBuf;
    RecordId tempRecId;


    memcpy(&number_of_keys, leafBuf + (2 * sizeof (int)), sizeof (int));

    pf.read(pid, leafBuf);

    //case for equality
    if (op == 1) {


        memcpy(&tempKey, leafBuf + 4 * sizeof (int), sizeof (int));


        while (tempKey < searchKey) {

            memcpy(&tempKey, leafBuf + 4 * sizeof (int) +(j + 1)* 3 * sizeof (int), sizeof (int));
            j += 1;

            if (j >= number_of_keys) {
                return EQUALITY_NOT_SATISFIED; //this is Equality case. and no records found.
            }
        }

        eid = j + 1;

    } else if (op == 2) // LESS THAN
    {
        //if tempKey < searchKey return True
        memcpy(&tempKey, leafBuf + 4 * sizeof (int) + (eid - 1) * 3 * sizeof (int), sizeof (int));

        if (tempKey < searchKey) {

            eid++;

            if (eid > number_of_keys) {
                eid = 1;

                memcpy(&siblingId, leafBuf + 3 * sizeof (int), sizeof (int));

                return siblingId;
            }

            return LESS_SATISFIED;
        } else {
            return INEQUALITY_NOT_SATISFIED;
        }

    } else if (op == 3) {
        memcpy(&tempKey, leafBuf + 4 * sizeof (int) + (eid - 1) * 3 * sizeof (int), sizeof (int));

        if (tempKey > searchKey) {

            eid++;

            if (eid > number_of_keys) {
                eid = 1;

                memcpy(&siblingId, leafBuf + 3 * sizeof (int), sizeof (int));

                return siblingId;
            }

            return GREATER_SATISFIED;
        } else {
            return INEQUALITY_NOT_SATISFIED;
        }

    } else if (op == 4) {
        memcpy(&tempKey, leafBuf + 4 * sizeof (int) + (eid - 1) * 3 * sizeof (int), sizeof (int));

        if (tempKey <= searchKey) {

            eid++;

            if (eid > number_of_keys) {
                eid = 1;

                memcpy(&siblingId, leafBuf + 3 * sizeof (int), sizeof (int));

                return siblingId;
            }

            return LESSEQUAL_SATISFIED;
        } else {
            return INEQUALITY_NOT_SATISFIED;
        }

    } else if (op == 5) {
        memcpy(&tempKey, leafBuf + 4 * sizeof (int) + (eid - 1) * 3 * sizeof (int), sizeof (int));

        if (tempKey >= searchKey) {

            eid++;

            if (eid > number_of_keys) {
                eid = 1;

                memcpy(&siblingId, leafBuf + 3 * sizeof (int), sizeof (int));

                return siblingId;
            }

            return GREATEREQUAL_SATISFIED;
        } else {
            return INEQUALITY_NOT_SATISFIED;
        }

    }

    
    
    
    
    
    
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid, PageId pid, PageFile pf) {

    void *leafBuf;
    pf.read(pid, leafBuf);
    memcpy(&rid, leafBuf + 4 * sizeof (int) +(eid - 1) * 2 * sizeof (int) + sizeof (int), 2 * sizeof (int));

    
    
    
    return 0;
    
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr() {
    return 0;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid) {
    return 0;
}

/**
 * Constructor
 * @param ppid
 * @param pid
 * @return 
 */
RC BTNonLeafNode::BTNonLeafNode(PageId ppid, PageId pid) {
    numkeys = 0;
    memcpy(buffer, &ppid, sizeof (int));
    memcpy(buffer + sizeof (int), &pid, sizeof (int));
    memcpy(buffer + 2 * sizeof (int), &numkeys, sizeof (int));
    hashmap[pid] = 'N';

    
    
    
    
    
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf) {
    return 0;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf) {
    return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount() {
    return 0;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
int BTNonLeafNode::insert(int key_above, PageId newNodeId, PageId parentid, PageFile &pf) {
    void* parentBuffer;
    int numberOfParentElements;

    pf.read(parentid, parentBuffer);
    
    memcpy(&numberOfParentElements, parentBuffer + 2 * sizeof (int), sizeof (int));

    //copy the Key_above variable and new page id into the parent Node
    memcpy(parentBuffer + 4 * sizeof (int) +numberOfParentElements * 2 * sizeof (int), &key_above, sizeof (int));
    memcpy(parentBuffer + 4 * sizeof (int) +numberOfParentElements * 2 * sizeof (int) + sizeof (int), &newNodeId, sizeof (int));
    //increase the number of parent elements by 1
    numberOfParentElements += 1;
    
    //SORT
    BTNonLeafNode::nonLeafSort(parentBuffer);
    
    memcpy(parentBuffer + 2 * sizeof (int), &numberOfParentElements, sizeof (int));
    
    pf.write(parentid, parentBuffer);

    return numberOfParentElements;

    
    
    
    
    
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(PageId pid, PageFile &pf, PageId &rootPid) {
    
    void *oldNodeBuffer, *grandParentBuffer;
    int parentid, newPageid,midindex,numberofrecords, midkey;
    int j=0, our_index;
    
    
    pf.read(pid, oldNodeBuffer);
    memcpy(&parentid, oldNodeBuffer, sizeof(int));
    
    newPageid = pf.endPid();
    
    BTNonLeafNode newSplitNode = new BTNonLeafNode(parentid, newPageid);
    
    memcpy(&numberofrecords,oldNodeBuffer+2*sizeof(int),sizeof(int));
    
    midindex=ceil((numberofrecords+1)/2);
    
    memcpy(&midkey, oldNodeBuffer+4*sizeof(int)+ (midindex-1) * 2* sizeof(int) , sizeof(int));
    
    memcpy(&our_index, oldNodeBuffer + 4 * sizeof (int) +midindex * 2 * sizeof (int) - sizeof (int), sizeof (int));
    j = 3 * sizeof (int);
    
    while (our_index <= (MAX_NONLEAF + 1)* 2 * sizeof (int) + 4 * sizeof (int)) {
        
        memcpy(newSplitNode.buffer + j, oldNodeBuffer + our_index, sizeof (int));

        our_index +=  sizeof (int);

        j += sizeof (int);
    }
    
    int newNodeCount = numberofrecords - midindex;
    int finalMidIndex = midindex - 1;
    
    memcpy(oldNodeBuffer+2*sizeof(int) , &finalMidIndex, sizeof(int));
    memcpy(newSplitNode.buffer+2*sizeof(int) , &newNodeCount, sizeof(int));
    
    //Writing back the modified NonLeaf Pages to DISK
    pf.write(pid, oldNodeBuffer);
    pf.write(newPageid, newSplitNode.buffer);
    
    /* NOW OUR NON LEAF NODES are COMMITTED */
    
    /***MODIFYING THE PARENT IDs OF THE CHILD NODES TO newSplitNode.buffer's pageID***/
    
    int i=0, childPid;
    void *childBuffer;

    while (i++ <= newNodeCount) {
        memcpy(&childPid, newSplitNode.buffer + 3 * sizeof (int) +i * 2 * sizeof (int), sizeof (int));
        pf.read(childPid, childBuffer);
        memcpy(childBuffer, newPageid, sizeof (int));
        pf.write(childPid, childBuffer);
    }
    
    int grandParentCount;
    if(pid == rootPid)
    {
        //NO ROOT ABOVE
        int newRootid = pf.endPid();
        BTNonLeafNode newRoot = new BTNonLeafNode(-1, newRootid);

        memcpy(newRoot.buffer+3*sizeof(int), &pid, sizeof(int));
        memcpy(newRoot.buffer+4*sizeof(int), &midkey, sizeof(int));
        memcpy(newRoot.buffer+5*sizeof(int), &newPageid, sizeof(int));
        
        rootPid = newRootid;
        
        
    } else {
        /*NOW Push it up and check for recursion*/
        pf.read(parentid, grandParentBuffer);

        memcpy(&grandParentCount, grandParentBuffer + 2 * sizeof (int), sizeof (int));

        memcpy(grandParentBuffer + 4 * sizeof (int) +(grandParentCount - 1)*2 * sizeof (int), midkey, sizeof (int));
        memcpy(grandParentBuffer + 4 * sizeof (int) +(grandParentCount - 1)*2 * sizeof (int) + sizeof (int), newPageid, sizeof (int));
        grandParentCount++;
        memcpy(grandParentBuffer + 2 * sizeof (int), &grandParentCount, sizeof (int));

        BTNonLeafNode::nonLeafSort(grandParentBuffer);

        if (grandParentCount > MAX_NONLEAF) {
            BTNonLeafNode::insertAndSplit(parentid, &pf, &rootPid);
        }
    }
    
    
    
    
    
    
    return 0;
    
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid, PageFile &pf) {

    int j = 0, tempKey, number_of_keys;
    void *nonLeafBuf;

    pf.read(pid, nonLeafBuf);

    memcpy(&number_of_keys, nonLeafBuf + (2 * sizeof (int)), sizeof (int));

    memcpy(&tempKey, nonLeafBuf + 4 * sizeof (int), sizeof (int));

    while (tempKey <= searchKey) {
        //keep traversing
        memcpy(&tempKey, nonLeafBuf + 4 * sizeof (int) +(j + 1)*2 * sizeof (int), sizeof (int));
        j += 1;
        if (j >= number_of_keys)
            break;
    }

    memcpy(&pid, nonLeafBuf + 3 * sizeof (int) +j * 2 * sizeof (int), sizeof (int));

    
    
    
    
    
    return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2) {
    
    memcpy(buffer + 3 * sizeof (int), &pid1, sizeof (int));
    memcpy(buffer + 4 * sizeof (int), &key, sizeof (int));
    memcpy(buffer + 5 * sizeof (int), &pid2, sizeof (int));
    
    
    
    
    
    return 0;
}

